package com.niuke;

/**
 * @ClassName : NC17
 * @Author : kele
 * @Date: 2023/4/8 17:13
 * @Description :
 */
public class NC17 {

    public static int getLongestPalindrome(String A) {

        int n = A.length();
        if (n <= 1) {
            return n;
        }
        boolean[][] dp = new boolean[n][n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            if (i < n - 1 && A.charAt(i) == A.charAt(i + 1)) {
                dp[i][i + 1] = true;
                max = 2;
            }
        }


        for (int l = 3; l <= n; l++) {

            for (int i = 0; i <= n - l; i++) {
                int j = i + l - 1;
                if (A.charAt(i) == A.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    if (max < l) {
                        max = l;
                    }
                }

            }

        }
        return max;
    }

    public static String getLongestPalindrome2(String A) {
        int n = A.length();
        if (n <= 1) {
            return A;
        }
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = A.charAt(i) == A.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                if (dp[i][j] && j - i + 1 > ans.length()) {
                    ans = A.substring(i, j + 1);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(getLongestPalindrome("bb"));
        System.out.println(getLongestPalindrome2("bb"));
    }

}
